package sort;

import java.util.Arrays;
import java.util.jar.JarEntry;

/**
 * 希尔排序
 */
public class ShellSort {
    public static void main(String[] args) {
        Integer[] arr = new Integer[]{9, 5, 8, 4, 2, 1};
        System.out.println(Arrays.toString(shell2(arr)));


    }

    public static Integer[] shell(Integer[] arr) {
        for (int gap = arr.length / 2; gap >= 1; gap /= 2) {
            for (int j = gap; j < arr.length; j++) {
                int temp = arr[j];
                int k = j - gap;
                while (k >= 0 && temp < arr[k]) {
                    arr[k + gap] = arr[k];
                    k -= gap;
                }
                arr[k + gap] = temp;
            }
        }
        return arr;
    }

    public static Integer[] shell2(Integer[] arr) {
        int gap = arr.length / 2;
        while (gap > 0){
            for (int i = gap; i < arr.length; i++) {
                int temp = arr[i];
                int j = i - gap;
                while (j >= 0 && temp < arr[j]) {
                    arr[j + gap] = arr[j];
                    j-=gap;
                }
                arr[j + gap] = temp;
            }
            gap /= 2;
        }
        return arr;
    }


}
